<!DOCTYPE html>












  


<html class="theme-next gemini use-motion" lang="zh-CN">
<head><meta name="generator" content="Hexo 3.9.0">
  <meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
<meta name="theme-color" content="#222">












<meta http-equiv="Cache-Control" content="no-transform">
<meta http-equiv="Cache-Control" content="no-siteapp">






















<link href="/blog/lib/font-awesome/css/font-awesome.min.css?v=4.7.0" rel="stylesheet" type="text/css">

<link href="/blog/css/main.css?v=6.4.2" rel="stylesheet" type="text/css">


  <link rel="apple-touch-icon" sizes="180x180" href="/blog/images/apple-touch-icon-next.png?v=6.4.2">


  <link rel="icon" type="image/png" sizes="32x32" href="/blog/images/favicon-32x32-next.png?v=6.4.2">


  <link rel="icon" type="image/png" sizes="16x16" href="/blog/images/favicon-16x16-next.png?v=6.4.2">


  <link rel="mask-icon" href="/blog/images/logo.svg?v=6.4.2" color="#222">









<script type="text/javascript" id="hexo.configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/blog/',
    scheme: 'Gemini',
    version: '6.4.2',
    sidebar: {"position":"left","display":"post","offset":12,"b2t":false,"scrollpercent":false,"onmobile":false},
    fancybox: false,
    fastclick: false,
    lazyload: false,
    tabs: true,
    motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
    algolia: {
      applicationID: '',
      apiKey: '',
      indexName: '',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    }
  };
</script>


  




  <meta name="description" content="整理一些常见算法题，梳理解题思路。类似这种题目不难，但是久了容易忘。对于这种事情，最好的处理方式就是写成博客记录下来。需要的时候翻一翻基本就知道是怎么回事了。">
<meta name="keywords" content="算法">
<meta property="og:type" content="article">
<meta property="og:title" content="JavaScript程序和算法">
<meta property="og:url" content="https://xit-edu.cn/2017/11/01/blog/programming-and-algorithms/programming-and-algorithms/index.html">
<meta property="og:site_name" content="厦门工学院">
<meta property="og:description" content="整理一些常见算法题，梳理解题思路。类似这种题目不难，但是久了容易忘。对于这种事情，最好的处理方式就是写成博客记录下来。需要的时候翻一翻基本就知道是怎么回事了。">
<meta property="og:locale" content="zh-CN">
<meta property="og:updated_time" content="2022-08-26T09:57:59.310Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="JavaScript程序和算法">
<meta name="twitter:description" content="整理一些常见算法题，梳理解题思路。类似这种题目不难，但是久了容易忘。对于这种事情，最好的处理方式就是写成博客记录下来。需要的时候翻一翻基本就知道是怎么回事了。">






  <link rel="canonical" href="https://xit-edu.cn/2017/11/01/blog/programming-and-algorithms/programming-and-algorithms/">



<script type="text/javascript" id="page.configurations">
  CONFIG.page = {
    sidebar: "",
  };
</script>

  <title>JavaScript程序和算法 | 厦门工学院</title>
  






  <script type="text/javascript">
    var _hmt = _hmt || [];
    (function() {
      var hm = document.createElement("script");
      hm.src = "https://hm.baidu.com/hm.js?d3f181d3d99fc3c240567d5b682eebd1";
      var s = document.getElementsByTagName("script")[0];
      s.parentNode.insertBefore(hm, s);
    })();
  </script>






  <noscript>
  <style type="text/css">
    .use-motion .motion-element,
    .use-motion .brand,
    .use-motion .menu-item,
    .sidebar-inner,
    .use-motion .post-block,
    .use-motion .pagination,
    .use-motion .comments,
    .use-motion .post-header,
    .use-motion .post-body,
    .use-motion .collection-title { opacity: initial; }

    .use-motion .logo,
    .use-motion .site-title,
    .use-motion .site-subtitle {
      opacity: initial;
      top: initial;
    }

    .use-motion {
      .logo-line-before i { left: initial; }
      .logo-line-after i { right: initial; }
    }
  </style>
</noscript>

</head>

<body itemscope itemtype="http://schema.org/WebPage" lang="zh-CN">

  
  
    
  

  <div class="container sidebar-position-left page-post-detail">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-wrapper">
  <div class="site-meta ">
    

    <div class="custom-logo-site-title">
      <a href="/blog/" class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">厦门工学院</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
    
      
        <p class="site-subtitle">软件研发工作室</p>
      
    
  </div>

  <div class="site-nav-toggle">
    <button aria-label="切换导航栏">
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>



<nav class="site-nav">
  
    <ul id="menu" class="menu">
      
        
        
        
          
          <li class="menu-item menu-item-home">
    <a href="/blog/" rel="section">
      <i class="menu-item-icon fa fa-fw fa-home"></i> <br>首页</a>
  </li>
        
        
        
          
          <li class="menu-item menu-item-archives">
    <a href="/blog/archives/" rel="section">
      <i class="menu-item-icon fa fa-fw fa-archive"></i> <br>归档</a>
  </li>
        
        
        
          
          <li class="menu-item menu-item-tags">
    <a href="/blog/tags/" rel="section">
      <i class="menu-item-icon fa fa-fw fa-tags"></i> <br>标签</a>
  </li>
        
        
        
          
          <li class="menu-item menu-item-categories">
    <a href="/blog/categories/" rel="section">
      <i class="menu-item-icon fa fa-fw fa-th"></i> <br>分类</a>
  </li>
        
        
        
          
          <li class="menu-item menu-item-works1">
    <a href="/blog/works1/" rel="section">
      <i class="menu-item-icon fa fa-fw fa-sitemap"></i> <br>H5小游戏1</a>
  </li>
        
        
        
          
          <li class="menu-item menu-item-works2">
    <a href="/blog/works2/" rel="section">
      <i class="menu-item-icon fa fa-fw fa-calendar"></i> <br>H5小游戏2</a>
  </li>
        
        
        
          
          <li class="menu-item menu-item-fiction">
    <a href="/blog/fiction/" rel="section">
      <i class="menu-item-icon fa fa-fw fa-heartbeat"></i> <br>大将军归来</a>
  </li>
        
        
        
          
          <li class="menu-item menu-item-about">
    <a href="/blog/about/" rel="section">
      <i class="menu-item-icon fa fa-fw fa-user"></i> <br>关于</a>
  </li>

      
      
    </ul>
  

  

  
</nav>



  



</div>
    </header>

    


    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          
            

          
          <div id="content" class="content">
            

  <div id="posts" class="posts-expand">
    

  

  
  
  

  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="https://xit-edu.cn/blog/2017/11/01/blog/programming-and-algorithms/programming-and-algorithms/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="对美好事物的向往，心中要充满强烈的愿望！">
      <meta itemprop="description" content="沉淀下来的知识，才是真正的财富！">
      <meta itemprop="image" content="/blog/images/avatar.gif">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="厦门工学院">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">JavaScript程序和算法
              
            
          </h1>
        

        <div class="post-meta">
          <span class="post-time">

            
            
            

            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              

              
                
              

              <time title="创建时间：2017-11-01 11:11:11" itemprop="dateCreated datePublished" datetime="2017-11-01T11:11:11+08:00">2017-11-01</time>
            

            
              

              
                
                <span class="post-meta-divider">|</span>
                

                <span class="post-meta-item-icon">
                  <i class="fa fa-calendar-check-o"></i>
                </span>
                
                  <span class="post-meta-item-text">更新于</span>
                
                <time title="修改时间：2022-08-26 17:57:59" itemprop="dateModified" datetime="2022-08-26T17:57:59+08:00">2022-08-26</time>
              
            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing"><a href="/blog/categories/算法/" itemprop="url" rel="index"><span itemprop="name">算法</span></a></span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        <p>整理一些常见算法题，梳理解题思路。类似这种题目不难，但是久了容易忘。对于这种事情，最好的处理方式就是写成博客记录下来。需要的时候翻一翻基本就知道是怎么回事了。</p>
<a id="more"></a>
<h2 id="算法"><a href="#算法" class="headerlink" title="算法"></a>算法</h2><h3 id="链表"><a href="#链表" class="headerlink" title="链表"></a>链表</h3><p>已知链表的数据结构如下</p>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">ListNode</span>(<span class="params">v</span>)</span>&#123;</span><br><span class="line">    <span class="keyword">this</span>.value=v</span><br><span class="line">    <span class="keyword">this</span>.next=<span class="literal">null</span></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h4 id="反转链表"><a href="#反转链表" class="headerlink" title="反转链表"></a>反转链表</h4><p>有一个链表，a-&gt;b-&gt;c。通过一个方法变成，a&lt;-b&lt;-c。</p>
<p>算法思路：用两个指针一前prev一后curr。<br>prev代表前面一个指针，curr代表当前指针。<br>每次都是把当前指针的next指向前面一个指针。<br>注意在修改当前对象的next指向的时候要先把next保存下来。<br>修改完后，prev和curr都往后移。<br>prev=curr，curr=刚才保存的next</p>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// null a -&gt; b -&gt; c</span></span><br><span class="line"><span class="comment">// |    |   </span></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">ReversalList</span>(<span class="params">pHead</span>)</span>&#123;</span><br><span class="line">    <span class="keyword">let</span> prev = <span class="literal">null</span></span><br><span class="line">    <span class="keyword">let</span> curr = pHead</span><br><span class="line">    <span class="keyword">while</span>(curr)&#123;</span><br><span class="line">        <span class="keyword">let</span> next = curr.next</span><br><span class="line">        curr.next = prev</span><br><span class="line">        prev = curr </span><br><span class="line">        curr = next</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> prev</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="keyword">let</span> a = <span class="keyword">new</span> ListNode(<span class="number">1</span>)</span><br><span class="line"><span class="keyword">let</span> b = <span class="keyword">new</span> ListNode(<span class="number">2</span>)</span><br><span class="line"><span class="keyword">let</span> c = <span class="keyword">new</span> ListNode(<span class="number">3</span>)</span><br><span class="line">a.next = b</span><br><span class="line">b.next = c</span><br><span class="line"></span><br><span class="line">ReversalList(a)</span><br><span class="line"><span class="built_in">console</span>.log(c)</span><br></pre></td></tr></table></figure>
<h4 id="判断是否有环"><a href="#判断是否有环" class="headerlink" title="判断是否有环"></a>判断是否有环</h4><p>标记法，循环整个链表，在每个节点加入标志位flag，如果循环完整个链表都没有flag那就是没有环，如果有flag则表示有环。</p>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//标记法</span></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">hasCycle</span>(<span class="params">head</span>)</span>&#123;</span><br><span class="line">    <span class="keyword">while</span>(head)&#123;</span><br><span class="line">        <span class="keyword">if</span>(head.flag) <span class="keyword">return</span> <span class="literal">true</span></span><br><span class="line">        head.flag = <span class="literal">true</span></span><br><span class="line">        head = head.next</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="literal">false</span></span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">//测试</span></span><br><span class="line"><span class="keyword">let</span> a = <span class="keyword">new</span> ListNode(<span class="number">1</span>)</span><br><span class="line"><span class="keyword">let</span> b = <span class="keyword">new</span> ListNode(<span class="number">2</span>)</span><br><span class="line"><span class="keyword">let</span> c = <span class="keyword">new</span> ListNode(<span class="number">3</span>)</span><br><span class="line"><span class="keyword">let</span> d = <span class="keyword">new</span> ListNode(<span class="number">4</span>)</span><br><span class="line">a.next = b</span><br><span class="line">b.next = c</span><br><span class="line">c.next = d</span><br><span class="line">d.next = a</span><br><span class="line"></span><br><span class="line"><span class="built_in">console</span>.log(hasCycle(a))</span><br></pre></td></tr></table></figure>
<p>JSON.stringify，对循环引用会导致溢出报错。还有，它对undefined无法转换，对属性是undefined转换过来直接丢失。</p>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//借助JSON.stringify</span></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">hasCycle</span>(<span class="params">head</span>)</span>&#123;</span><br><span class="line">    <span class="keyword">try</span>&#123;</span><br><span class="line">        <span class="built_in">JSON</span>.stringify(head)</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">false</span></span><br><span class="line">    &#125;<span class="keyword">catch</span>(e)&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">true</span></span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h4 id="合并两个有序链表"><a href="#合并两个有序链表" class="headerlink" title="合并两个有序链表"></a>合并两个有序链表</h4><p>输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。<br>数据范围：0≤n≤1000，−1000≤节点值≤1000<br>要求：空间复杂度 O(1)，时间复杂度 O(n)</p>
<p>如输入{1,3,5},{2,4,6}时，合并后的链表为{1,2,3,4,5,6}，所以对应的输出为{1,2,3,4,5,6}，转换过程如下图所示：</p>
<p>解题思路一：循环链表，每次对比两个链表的数值，把最小的插入到数组里面，最后再判断两个链表是否都循环结束。</p>
<ol>
<li>循环pHead1和pHead2两个链表，每次取最小值插入到数组arr，被取出的链表要往下移。</li>
<li>用循环分别判断一下pHead1和pHead2是否都结束了，把没结束的插入到数组中。</li>
<li>循环数组，构建链表。</li>
</ol>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//循环链表，结合数组的方式。</span></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">Merge</span>(<span class="params">pHead1, pHead2</span>)</span>&#123;</span><br><span class="line">    <span class="keyword">let</span> arr = []</span><br><span class="line">    <span class="keyword">while</span>(pHead1 &amp;&amp; pHead2)&#123;</span><br><span class="line">        <span class="keyword">if</span>(pHead1.val &lt; pHead2.val)&#123;</span><br><span class="line">            arr.push(pHead1.val)</span><br><span class="line">            pHead1 = pHead1.next</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            arr.push(pHead2.val)</span><br><span class="line">            pHead2 = pHead2.next</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">while</span>(pHead1)&#123;</span><br><span class="line">        arr.push(pHead1.val)</span><br><span class="line">        pHead1 = pHead1.next</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">while</span>(pHead2)&#123;</span><br><span class="line">        arr.push(pHead2.val)</span><br><span class="line">        pHead2 = pHead2.next</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">let</span> result</span><br><span class="line">    <span class="keyword">let</span> temp</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">let</span> i=<span class="number">0</span>;i&lt;arr.length;i++)&#123;</span><br><span class="line">        <span class="comment">//注意：如果temp要放在循环里面，要用var，否则let是块级作用域，会每次循环都是一个新的temp。所以为了避免歧义，干脆把temp放到外面一个块级区域里面。</span></span><br><span class="line">        <span class="comment">//let temp</span></span><br><span class="line">        <span class="comment">//var temp</span></span><br><span class="line">        <span class="keyword">if</span>(i==<span class="number">0</span>)&#123;</span><br><span class="line">            temp = <span class="keyword">new</span> ListNode(arr[i])</span><br><span class="line">            result = temp</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            temp.next = <span class="keyword">new</span> ListNode(arr[i])</span><br><span class="line">            temp = temp.next</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> result</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>解题思路二：循环链表，不借助数组，在每次构建链表节点。</p>
<ol>
<li>先构建一个根节点root。</li>
<li>把根节点root引用赋值给当前节点curr，并且在初始的时候让curr的next指向下一个节点，这样root和curr的next都会指向这个节点。</li>
<li>然后把当前节点往下移curr = curr.next，还有被取出值的链表也往下移LinkList1 = LinkList1.next，没有取出值的就不用往下移LinkList2不变。</li>
<li>最后再判断一下LinkList1和LinkList2是否都空了。因为有可能LinkList1全部都小于LinkList2，这样在<code>while(pHead1 &amp;&amp; pHead2){...}</code>循环的时候，有可能只是其中一个遍历结束了，还有另外一个没有遍历结束。<br>这种方法要特别注意：当前节点对比完后，curr和LinkList都要往下移。</li>
</ol>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">Merge</span>(<span class="params">pHead1, pHead2</span>)</span>&#123;</span><br><span class="line">    <span class="keyword">let</span> root = <span class="keyword">new</span> ListNode(<span class="number">-1</span>)</span><br><span class="line">    <span class="keyword">let</span> curr = root</span><br><span class="line">    <span class="keyword">while</span>(pHead1 &amp;&amp; pHead2)&#123;</span><br><span class="line">        <span class="keyword">if</span>(pHead1.val &lt; pHead2.val)&#123;</span><br><span class="line">            curr.next = pHead1</span><br><span class="line">            pHead1 = pHead1.next</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            curr.next = pHead2</span><br><span class="line">            pHead2 = pHead2.next</span><br><span class="line">        &#125;</span><br><span class="line">        curr = curr.next</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//考虑到链表是有序的并且都已经连接在一起，所以这里其实是没有必要这样循环的，可以参考pHead2</span></span><br><span class="line">    <span class="comment">//但是这种思路更加通用，不仅适用于链表，同时也适用于数组。</span></span><br><span class="line">    <span class="keyword">while</span>(pHead1)&#123;</span><br><span class="line">        curr.next = pHead1</span><br><span class="line">        curr = curr.next</span><br><span class="line">        pHead1 = pHead1.next</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//所以其实只要这样就可以了。</span></span><br><span class="line">    <span class="keyword">if</span>(pHead2)&#123;</span><br><span class="line">        curr.next = pHead2</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> root.next</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h4 id="删除链表倒数第n个节点"><a href="#删除链表倒数第n个节点" class="headerlink" title="删除链表倒数第n个节点"></a>删除链表倒数第n个节点</h4><p>方法一：双指针<br>例如：删除倒数第2个元素，刚开始两个指针都指向a<br>a -&gt; b -&gt; c -&gt; d -&gt; e -&gt; NULL<br>||</p>
<p>删除倒数第2个节点，先让第一个指针动2步。<br>a -&gt; b -&gt; c -&gt; d -&gt; e -&gt; NULL<br>|         |</p>
<p>然后第二个指针和第一个指针，同时开始往后移动，直到第一个指针指到最后一个节点。<br>a -&gt; b -&gt; c -&gt; d -&gt; e -&gt; NULL<br>          |         |</p>
<p>这时候第二个指针事项从，它的下一个节点d，就是要被删掉的了。</p>
<p>方法二：链表的长度是5，要删除倒数第2个节点，就是删除从正向数的第5-2+1=4个节点。<br>即链表长度L，删除倒数第n个元素，相当于从正向数过去的第L-n+1个节点，要删除第4个节点，就要在第5-2=3个节点操作。</p>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// 方法一：双链表</span></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">removeNthFromEnd</span>(<span class="params"> head ,  n </span>) </span>&#123;</span><br><span class="line">    <span class="keyword">let</span> first = head</span><br><span class="line">    <span class="keyword">let</span> second = head</span><br><span class="line">    <span class="keyword">while</span>(n&gt;<span class="number">0</span>)&#123;</span><br><span class="line">        first = first.next</span><br><span class="line">        n--</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span>(!first) <span class="keyword">return</span> head.next</span><br><span class="line">    <span class="keyword">while</span>(first.next)&#123;</span><br><span class="line">        first = first.next</span><br><span class="line">        second = second.next</span><br><span class="line">    &#125;</span><br><span class="line">    second.next = second.next.next</span><br><span class="line">    <span class="keyword">return</span> head</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">// 方法二：利用L-n+1的对应关系，算出第几个节点是要删掉的。</span></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">removeNthFromEnd</span>(<span class="params"> head ,  n </span>) </span>&#123;</span><br><span class="line">    <span class="keyword">let</span> i=<span class="number">0</span></span><br><span class="line">    <span class="keyword">let</span> curr = head</span><br><span class="line">    <span class="keyword">while</span>(curr)&#123;</span><br><span class="line">        i++</span><br><span class="line">        curr = curr.next</span><br><span class="line">    &#125;<span class="comment">//先计算链表长度</span></span><br><span class="line">    <span class="comment">//有可能删除第一个节点</span></span><br><span class="line">    <span class="keyword">if</span>(i===n)<span class="keyword">return</span> head.next</span><br><span class="line">    curr = head</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">let</span> j=<span class="number">1</span>;j&lt;=i;j++)&#123;</span><br><span class="line">        <span class="comment">//要删除第i-n+1个，就要在第i-n+1的前一个进行操作，也就是在第i-n个操作</span></span><br><span class="line">        <span class="keyword">if</span>(j===i-n)&#123;</span><br><span class="line">            curr.next = curr.next.next</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            curr = curr.next</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> head</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h4 id="单链表的排序"><a href="#单链表的排序" class="headerlink" title="单链表的排序"></a>单链表的排序</h4><figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">sortInList</span>(<span class="params"> head </span>) </span>&#123;</span><br><span class="line">    <span class="keyword">let</span> arr = []</span><br><span class="line">    <span class="keyword">let</span> curr = head</span><br><span class="line">    <span class="comment">// 先把链表里面的数据一个个取出来放到数组里面。</span></span><br><span class="line">    <span class="keyword">while</span>(curr)&#123;</span><br><span class="line">        arr.push(curr.val)</span><br><span class="line">        curr = curr.next</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 对数组进行排序。</span></span><br><span class="line">    arr.sort(<span class="function">(<span class="params">a,b</span>)=&gt;</span>(a-b))</span><br><span class="line">    <span class="comment">// 构造新的链表</span></span><br><span class="line">    <span class="keyword">let</span> root,temp</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">let</span> i=<span class="number">0</span>;i&lt;arr.length;i++)&#123;</span><br><span class="line">        <span class="keyword">if</span>(i===<span class="number">0</span>)&#123;</span><br><span class="line">            root = <span class="keyword">new</span> ListNode(arr[i])</span><br><span class="line">            temp = root</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            temp.next = <span class="keyword">new</span> ListNode(arr[i])</span><br><span class="line">            temp = temp.next</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> root</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="栈和队列"><a href="#栈和队列" class="headerlink" title="栈和队列"></a>栈和队列</h3><p>用两个栈实现队列。如果不用栈也可以用push和shift实现队列。</p>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//构造栈的数据结构。</span></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">Stack</span>(<span class="params"></span>)</span>&#123;</span><br><span class="line">    <span class="keyword">this</span>.item=[]</span><br><span class="line">    <span class="keyword">this</span>.push=<span class="function"><span class="keyword">function</span>(<span class="params">v</span>)</span>&#123;</span><br><span class="line">        <span class="keyword">this</span>.item.push(v)</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">this</span>.pop=<span class="function"><span class="keyword">function</span>(<span class="params"></span>)</span>&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">this</span>.item.pop()</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">this</span>.length=<span class="function"><span class="keyword">function</span>(<span class="params"></span>)</span>&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">this</span>.item.length</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="keyword">let</span> stack1 = <span class="keyword">new</span> Stack()</span><br><span class="line"><span class="keyword">let</span> stack2 = <span class="keyword">new</span> Stack()</span><br><span class="line"></span><br><span class="line"><span class="comment">//插入数据都到栈1</span></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">push</span>(<span class="params">node</span>)</span>&#123;</span><br><span class="line">    stack1.push(node)</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">//返回数据都从栈2返回，但是栈2的数据来源于栈1，它需要先把栈1的数据全部出栈，并且按照出栈的顺序入栈到栈2。这样的顺序就是队列的顺序，然后再从栈2全部返回。</span></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">pop</span>(<span class="params"></span>)</span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(stack2.length()&gt;<span class="number">0</span>)&#123;</span><br><span class="line">        <span class="keyword">return</span> stack2.pop()</span><br><span class="line">    &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">        <span class="keyword">while</span>(stack1.length()&gt;<span class="number">0</span>)&#123;</span><br><span class="line">            <span class="keyword">let</span> v = stack1.pop()</span><br><span class="line">            stack2.push(v)</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> stack2.pop()</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">&#125;</span><br><span class="line">push(<span class="number">1</span>)</span><br><span class="line">push(<span class="number">2</span>)</span><br><span class="line">push(<span class="number">3</span>)</span><br><span class="line"><span class="built_in">console</span>.log(pop())</span><br><span class="line"><span class="built_in">console</span>.log(pop())</span><br><span class="line"><span class="built_in">console</span>.log(pop())</span><br><span class="line"><span class="built_in">console</span>.log(pop())</span><br></pre></td></tr></table></figure>
<h3 id="二分查找"><a href="#二分查找" class="headerlink" title="二分查找"></a>二分查找</h3><p>左边下标left，右边一个下标right，中间标middle取left和right之和的中间值。<br>如果要查找的target，等于middle下标指向的值，那么right=middle-1。不能直接return，因为在前面可能还有，我们要查找最早出现的位置<br>如果要查找的target，小于middle下标指向的值，那么right=middle-1。<br>如果要查找的target，大于middle下标指向的值，那么left=middle+1。</p>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">search</span>(<span class="params"> nums ,  target </span>) </span>&#123;</span><br><span class="line">    <span class="keyword">let</span> index =<span class="number">-1</span>;</span><br><span class="line">    <span class="keyword">let</span> left = <span class="number">0</span>,</span><br><span class="line">    right = nums.length - <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">while</span>(left &lt;= right)&#123;</span><br><span class="line">        <span class="keyword">let</span> midle = <span class="built_in">Math</span>.floor((left + right) / <span class="number">2</span>);</span><br><span class="line">        <span class="keyword">if</span>(target == nums[midle])&#123;</span><br><span class="line">            index = midle;</span><br><span class="line">            right = midle <span class="number">-1</span>;<span class="comment">//这一步是为了当等于中值的时候继续往前走，保证输出的是第一次出现的位置</span></span><br><span class="line">        &#125;<span class="keyword">else</span> <span class="keyword">if</span>(target &lt; nums[midle])&#123;</span><br><span class="line">            right = midle <span class="number">-1</span>;</span><br><span class="line">        &#125;<span class="keyword">else</span> <span class="keyword">if</span>(target &gt; nums[midle])&#123;</span><br><span class="line">            left = midle + <span class="number">1</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> index</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="斐波那切数列"><a href="#斐波那切数列" class="headerlink" title="斐波那切数列"></a>斐波那切数列</h3><figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//0,1,1,2,3,5,8</span></span><br><span class="line"><span class="comment">//递归。这种方法在number=50的时候会溢出。</span></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">jumpFloor</span>(<span class="params">number</span>)</span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(number&lt;=<span class="number">0</span>) <span class="keyword">return</span> <span class="number">0</span></span><br><span class="line">    <span class="keyword">if</span>(number==<span class="number">1</span>) <span class="keyword">return</span> <span class="number">1</span></span><br><span class="line">    <span class="keyword">if</span>(number==<span class="number">2</span>) <span class="keyword">return</span> <span class="number">1</span></span><br><span class="line">    <span class="keyword">return</span> jumpFloor(number<span class="number">-1</span>)+jumpFloor(number<span class="number">-2</span>)</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">//计算.这种方法无论number等于多少都不会溢出。</span></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">jumpFloor</span>(<span class="params">n</span>)</span></span><br><span class="line"><span class="function">    <span class="title">let</span> <span class="title">number1</span>=1</span></span><br><span class="line"><span class="function">    <span class="title">let</span> <span class="title">number2</span>=1</span></span><br><span class="line"><span class="function">    <span class="title">if</span>(<span class="params">n==<span class="number">0</span></span>)<span class="title">return</span> 0</span></span><br><span class="line"><span class="function">    <span class="title">if</span>(<span class="params">n==<span class="number">1</span></span>)<span class="title">return</span> 1</span></span><br><span class="line"><span class="function">    <span class="title">if</span>(<span class="params">n==<span class="number">2</span></span>)<span class="title">return</span> 1</span></span><br><span class="line"><span class="function">    <span class="title">let</span> <span class="title">result</span> =0</span></span><br><span class="line"><span class="function">    <span class="title">for</span>(<span class="params">let i = <span class="number">3</span>;i&lt;=n;i++</span>)</span>&#123;</span><br><span class="line">        result = number1+number2</span><br><span class="line">        number1 = number2</span><br><span class="line">        number2 = result</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> result</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="翻转字符串"><a href="#翻转字符串" class="headerlink" title="翻转字符串"></a>翻转字符串</h3><figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 反转字符串</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param </span>str string字符串 </span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return </span>string字符串</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">solve</span>(<span class="params">str</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(!str) <span class="keyword">return</span> <span class="string">''</span></span><br><span class="line">    <span class="keyword">let</span> newStr = <span class="string">''</span></span><br><span class="line">    <span class="keyword">let</span> n = str.length - <span class="number">1</span></span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">let</span> i=n; i&gt;=<span class="number">0</span>; i--)&#123;</span><br><span class="line">        newStr += str.charAt(i)</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> newStr</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="数组"><a href="#数组" class="headerlink" title="数组"></a>数组</h3><h4 id="快速排序"><a href="#快速排序" class="headerlink" title="快速排序"></a>快速排序</h4><p>分治思想，分而治之。</p>
<ul>
<li>取数组中间位置，作为哨兵。</li>
<li>小于哨兵的放在left数组，不小于哨兵的放在right。</li>
<li>把三个数组连接起来</li>
</ul>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">quickSort</span>(<span class="params">arr</span>)</span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(arr.length&lt;=<span class="number">1</span>) <span class="keyword">return</span> arr</span><br><span class="line">    <span class="keyword">let</span> pivotIndex = <span class="built_in">Math</span>.floor(arr.length/<span class="number">2</span>)</span><br><span class="line">    <span class="keyword">let</span> pivot = arr.splice(pivotIndex,<span class="number">1</span>)[<span class="number">0</span>]</span><br><span class="line">    <span class="keyword">let</span> left = []</span><br><span class="line">    <span class="keyword">let</span> right = []</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">let</span> i=<span class="number">0</span>;i&lt;arr.length;i++)&#123;</span><br><span class="line">        <span class="keyword">if</span>(arr[i]&lt;pivot)&#123;</span><br><span class="line">            left.push(arr[i])</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            right.push(arr[i])</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> quickSort(left).concat([pivot],quickSort(right))</span><br><span class="line">&#125;</span><br><span class="line"><span class="keyword">let</span> a = [<span class="number">8</span>,<span class="number">3</span>,<span class="number">3</span>,<span class="number">5</span>,<span class="number">6</span>]</span><br><span class="line"></span><br><span class="line"><span class="built_in">console</span>.log(quickSort(a))</span><br></pre></td></tr></table></figure>
<h4 id="NC119-最小的K个数"><a href="#NC119-最小的K个数" class="headerlink" title="NC119 最小的K个数"></a>NC119 最小的K个数</h4><p>给定一个长度为 n 的可能有重复值的数组，找出其中不去重的最小的 k 个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4(任意顺序皆可)。<br>数据范围：0 ≤ k,n≤10000，数组中每个数的大小 0 ≤ val ≤ 1000<br>要求：空间复杂度 O(n)O(n) ，时间复杂度 O(nlogn)O(nlogn)</p>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// 方法一：直接排序，然后去前k小数据。</span></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">GetLeastNumbers_Solution</span>(<span class="params">input, k</span>)</span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="comment">// write code here</span></span><br><span class="line">    input.sort(<span class="function">(<span class="params">a,b</span>)=&gt;</span>(a - b))</span><br><span class="line">    <span class="keyword">return</span> input.slice(<span class="number">0</span>,k)</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">// 方法二：借鉴快速排序的思想。</span></span><br><span class="line"><span class="comment">// 取一个值，小于这个值的放左边，看数组个数如果刚好等于k，就是最小k个数。这样不行，因为如果存在相同的数字，那么k可能永远都不会相等。</span></span><br><span class="line"><span class="comment">// 其实最好的办法，先获得一个有序数组，然后取这个数组的前n个元素</span></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">GetLeastNumbers_Solution</span>(<span class="params">input, k</span>)</span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">let</span> arr = quickSort(input)</span><br><span class="line">    <span class="keyword">let</span> result = []</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">let</span> i=<span class="number">0</span>;i&lt;k;i++)&#123;</span><br><span class="line">        result.push(arr[i])</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> result</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">quickSort</span>(<span class="params">arr</span>)</span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(arr.length&lt;=<span class="number">1</span>) <span class="keyword">return</span> arr</span><br><span class="line">    <span class="keyword">let</span> pivotIndex = <span class="built_in">Math</span>.floor(arr.length/<span class="number">2</span>)</span><br><span class="line">    <span class="keyword">let</span> pivot = arr.splice(pivotIndex,<span class="number">1</span>)[<span class="number">0</span>]</span><br><span class="line">    <span class="keyword">let</span> left = []</span><br><span class="line">    <span class="keyword">let</span> right = []</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">let</span> i=<span class="number">0</span>;i&lt;arr.length;i++)&#123;</span><br><span class="line">        <span class="keyword">if</span>(arr[i]&lt;pivot)&#123;</span><br><span class="line">            left.push(arr[i])</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            right.push(arr[i])</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> quickSort(left).concat([pivot],quickSort(right))</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h4 id="NC22-合并两个有序的数组"><a href="#NC22-合并两个有序的数组" class="headerlink" title="NC22 合并两个有序的数组"></a>NC22 合并两个有序的数组</h4><p>给出一个有序的整数数组 A 和有序的整数数组 B ，请将数组 B 合并到数组 A 中，变成一个有序的升序数组<br>数据范围： 0≤n ， m≤100，|A_i| &lt;= 100∣，|B_i| &lt;= 100 </p>
<p>注意：<br>1.保证 A 数组有足够的空间存放 B 数组的元素， A 和 B 中初始的元素数目分别为 m 和 n，A的数组空间大小为 m+n<br>2.不要返回合并的数组，将数组 B 的数据合并到 A 里面就好了<br>3.A 数组在<code>[0,m-1]</code>的范围也是有序的</p>
<p>理解题目可知：</p>
<ul>
<li>A是有序的，B是有序的</li>
<li>A的空间刚好足够放下B</li>
</ul>
<p>解题思路：</p>
<ul>
<li>两个指针a,b分别指向A,B数组</li>
<li>第三根指针k，从A数组最后往前遍历。为什么要从后往前呢？因为A,B都是有序的，所以从后往前比较大的在后面小的在前门，这样指针k所指之处只需赋值一次就行了。</li>
</ul>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param </span>A int整型一维数组 </span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param </span>B int整型一维数组 </span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="variable">void</span></span></span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">merge</span>(<span class="params"> A, m, B, n </span>) </span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(n==<span class="number">0</span>)<span class="keyword">return</span> A</span><br><span class="line">    <span class="keyword">let</span> i=m<span class="number">-1</span>,j=n<span class="number">-1</span><span class="comment">//i是A数组的下标，j是B数组的下标</span></span><br><span class="line">    <span class="keyword">let</span> k=m+n<span class="number">-1</span><span class="comment">//k是结果的下标</span></span><br><span class="line">    <span class="keyword">while</span>(i&gt;=<span class="number">0</span> &amp;&amp; j&gt;=<span class="number">0</span>)&#123;<span class="comment">//k指针先从结果数组从后往前执行</span></span><br><span class="line">        A[k--]=A[i]&gt;B[j]?A[i--]:B[j--]</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//按照这种算法，有可能k还没执行完，但是i或j其中一个先执行完了。导致第一次while的条件不满足。</span></span><br><span class="line">    <span class="keyword">while</span>(i&gt;=<span class="number">0</span>)&#123;<span class="comment">//A还有剩。例如：A的数组都是比B小的，导致 i-- 一次都没执行</span></span><br><span class="line">        A[k--] = A[i--]</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">while</span>(j&gt;=<span class="number">0</span>)&#123;<span class="comment">//B还有剩。例如：B的数组都是比A小的，导致 j-- 一次都没执行</span></span><br><span class="line">        A[k--] = B[j--]</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">// 测试</span></span><br><span class="line"><span class="keyword">let</span> A = [<span class="number">1</span>,<span class="number">2</span>,<span class="number">3</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>]</span><br><span class="line"><span class="keyword">let</span> B = [<span class="number">4</span>,<span class="number">5</span>,<span class="number">6</span>]</span><br><span class="line">merge(A,<span class="number">3</span>,B,<span class="number">3</span>)</span><br><span class="line"><span class="built_in">console</span>.log(A)</span><br><span class="line"><span class="comment">// 输出：[1,2,3,4,5,6]</span></span><br></pre></td></tr></table></figure>
<h3 id="二叉树"><a href="#二叉树" class="headerlink" title="二叉树"></a>二叉树</h3><figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line">二叉树的数据结构。</span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">TreeNode</span>(<span class="params">x</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">this</span>.val = x;</span><br><span class="line">    <span class="keyword">this</span>.left = <span class="literal">null</span>;</span><br><span class="line">    <span class="keyword">this</span>.right = <span class="literal">null</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h4 id="前序遍历、中序遍历、后续遍历"><a href="#前序遍历、中序遍历、后续遍历" class="headerlink" title="前序遍历、中序遍历、后续遍历"></a>前序遍历、中序遍历、后续遍历</h4><figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param </span>root TreeNode类 the root of binary tree</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return </span>int整型二维数组</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">threeOrders</span>(<span class="params"> root </span>) </span>&#123;</span><br><span class="line">    <span class="keyword">let</span> preNodes=[],inNodes=[],postNodes=[]</span><br><span class="line">    <span class="function"><span class="keyword">function</span> <span class="title">preorder</span>(<span class="params">root</span>)</span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(!root) <span class="keyword">return</span> </span><br><span class="line">        preNodes.push(root.val)<span class="comment">//根</span></span><br><span class="line">        preorder(root.left)<span class="comment">//左</span></span><br><span class="line">        preorder(root.right)<span class="comment">//右</span></span><br><span class="line">    &#125;</span><br><span class="line">    <span class="function"><span class="keyword">function</span> <span class="title">inorder</span>(<span class="params">root</span>)</span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(!root) <span class="keyword">return</span> </span><br><span class="line">        inorder(root.left)<span class="comment">//左</span></span><br><span class="line">        inNodes.push(root.val)<span class="comment">//根</span></span><br><span class="line">        inorder(root.right)<span class="comment">//右</span></span><br><span class="line">    &#125;</span><br><span class="line">    <span class="function"><span class="keyword">function</span> <span class="title">postorder</span>(<span class="params">root</span>)</span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(!root) <span class="keyword">return</span> </span><br><span class="line">        postorder(root.left)<span class="comment">//左</span></span><br><span class="line">        postorder(root.right)<span class="comment">//右</span></span><br><span class="line">        postNodes.push(root.val)<span class="comment">//根</span></span><br><span class="line">    &#125;</span><br><span class="line">    preorder(root)<span class="comment">//执行前序遍历</span></span><br><span class="line">    inorder(root)<span class="comment">//执行中序遍历</span></span><br><span class="line">    postorder(root)<span class="comment">//执行后续遍历</span></span><br><span class="line">    <span class="keyword">return</span> [preNodes,inNodes,postNodes]</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">// 测试</span></span><br><span class="line"><span class="keyword">let</span> a = <span class="keyword">new</span> TreeNode(<span class="number">1</span>)</span><br><span class="line"><span class="keyword">let</span> b = <span class="keyword">new</span> TreeNode(<span class="number">2</span>)</span><br><span class="line"><span class="keyword">let</span> c = <span class="keyword">new</span> TreeNode(<span class="number">3</span>)</span><br><span class="line">a.left = b</span><br><span class="line">a.right = c</span><br><span class="line">threeOrders(a)</span><br><span class="line"></span><br><span class="line"><span class="comment">// 输出：[[1,2,3],[2,1,3],[2,3,1]]</span></span><br></pre></td></tr></table></figure>
<h4 id="层次遍历"><a href="#层次遍历" class="headerlink" title="层次遍历"></a>层次遍历</h4><p>深度优先遍历(Depth First Search, 简称 DFS) 与广度优先遍历(Breath First Search, 简称BFS)</p>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">levelOrder</span>(<span class="params">root</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">let</span> res=[],index=<span class="number">0</span></span><br><span class="line">    <span class="function"><span class="keyword">function</span> <span class="title">bfs</span>(<span class="params">root,index</span>)</span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(!root) <span class="keyword">return</span> </span><br><span class="line">        <span class="comment">//index表示深度，就是现在是第几层，从第0层开始是根节点，然后一直往下。</span></span><br><span class="line">        <span class="comment">//因为二叉树是肯定不会断开的，所以index肯定是连续的。每一层至少会有一个元素。不可能这一层没有节点，下一层有节点。</span></span><br><span class="line">        <span class="keyword">if</span>(index&gt;=res.length) res[index]=[]</span><br><span class="line">        res[index].push(root.val)</span><br><span class="line">        bfs(root.left,index+<span class="number">1</span>)</span><br><span class="line">        bfs(root.right,index+<span class="number">1</span>)</span><br><span class="line">    &#125;</span><br><span class="line">    bfs(root,index)</span><br><span class="line">    <span class="keyword">return</span> res</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">// 测试</span></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">TreeNode</span>(<span class="params">x</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">this</span>.val = x;</span><br><span class="line">    <span class="keyword">this</span>.left = <span class="literal">null</span>;</span><br><span class="line">    <span class="keyword">this</span>.right = <span class="literal">null</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="keyword">let</span> a = <span class="keyword">new</span> TreeNode(<span class="number">3</span>)</span><br><span class="line"><span class="keyword">let</span> b = <span class="keyword">new</span> TreeNode(<span class="number">9</span>)</span><br><span class="line"><span class="keyword">let</span> c = <span class="keyword">new</span> TreeNode(<span class="number">20</span>)</span><br><span class="line"><span class="keyword">let</span> d = <span class="keyword">new</span> TreeNode(<span class="number">15</span>)</span><br><span class="line"><span class="keyword">let</span> e = <span class="keyword">new</span> TreeNode(<span class="number">7</span>)</span><br><span class="line">a.left = b</span><br><span class="line">a.right = c</span><br><span class="line">c.left = d </span><br><span class="line">c.right = e</span><br><span class="line"></span><br><span class="line">levelOrder(a)</span><br></pre></td></tr></table></figure>

      
    </div>

    

    
    
    

    

    

    

    <footer class="post-footer">
      
        <div class="post-tags">
          
            <a href="/blog/tags/算法/" rel="tag"># 算法</a>
          
        </div>
      

      
      
      

      
        <div class="post-nav">
          <div class="post-nav-next post-nav-item">
            
              <a href="/blog/2016/01/03/blog/hexo/hexo/" rel="next" title="使用hexo搭建个人博客">
                <i class="fa fa-chevron-left"></i> 使用hexo搭建个人博客
              </a>
            
          </div>

          <span class="post-nav-divider"></span>

          <div class="post-nav-prev post-nav-item">
            
              <a href="/blog/2017/11/03/blog/web-front-end-basic/web-front-end-basic/" rel="prev" title="Web前端基础">
                Web前端基础 <i class="fa fa-chevron-right"></i>
              </a>
            
          </div>
        </div>
      

      
      
    </footer>
  </div>
  
  
  
  </article>


  </div>


          </div>
          

  



        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    
    <div class="sidebar-inner">

      

      
        <ul class="sidebar-nav motion-element">
          <li class="sidebar-nav-toc sidebar-nav-active" data-target="post-toc-wrap">
            文章目录
          </li>
          <li class="sidebar-nav-overview" data-target="site-overview-wrap">
            站点概览
          </li>
        </ul>
      

      <section class="site-overview-wrap sidebar-panel">
        <div class="site-overview">
          <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
            
              <p class="site-author-name" itemprop="name">对美好事物的向往，心中要充满强烈的愿望！</p>
              <p class="site-description motion-element" itemprop="description">沉淀下来的知识，才是真正的财富！</p>
          </div>

          
            <nav class="site-state motion-element">
              
                <div class="site-state-item site-state-posts">
                
                  <a href="/blog/archives/">
                
                    <span class="site-state-item-count">19</span>
                    <span class="site-state-item-name">日志</span>
                  </a>
                </div>
              

              
                
                
                <div class="site-state-item site-state-categories">
                  <a href="/blog/categories/index.html">
                    
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                    <span class="site-state-item-count">22</span>
                    <span class="site-state-item-name">分类</span>
                  </a>
                </div>
              

              
                
                
                <div class="site-state-item site-state-tags">
                  <a href="/blog/tags/index.html">
                    
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                    <span class="site-state-item-count">19</span>
                    <span class="site-state-item-name">标签</span>
                  </a>
                </div>
              
            </nav>
          

          

          

          
          

          
          

          
            
          
          

        </div>
      </section>

      
      <!--noindex-->
        <section class="post-toc-wrap motion-element sidebar-panel sidebar-panel-active">
          <div class="post-toc">

            
              
            

            
              <div class="post-toc-content"><ol class="nav"><li class="nav-item nav-level-2"><a class="nav-link" href="#算法"><span class="nav-number">1.</span> <span class="nav-text">算法</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#链表"><span class="nav-number">1.1.</span> <span class="nav-text">链表</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#反转链表"><span class="nav-number">1.1.1.</span> <span class="nav-text">反转链表</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#判断是否有环"><span class="nav-number">1.1.2.</span> <span class="nav-text">判断是否有环</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#合并两个有序链表"><span class="nav-number">1.1.3.</span> <span class="nav-text">合并两个有序链表</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#删除链表倒数第n个节点"><span class="nav-number">1.1.4.</span> <span class="nav-text">删除链表倒数第n个节点</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#单链表的排序"><span class="nav-number">1.1.5.</span> <span class="nav-text">单链表的排序</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#栈和队列"><span class="nav-number">1.2.</span> <span class="nav-text">栈和队列</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#二分查找"><span class="nav-number">1.3.</span> <span class="nav-text">二分查找</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#斐波那切数列"><span class="nav-number">1.4.</span> <span class="nav-text">斐波那切数列</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#翻转字符串"><span class="nav-number">1.5.</span> <span class="nav-text">翻转字符串</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#数组"><span class="nav-number">1.6.</span> <span class="nav-text">数组</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#快速排序"><span class="nav-number">1.6.1.</span> <span class="nav-text">快速排序</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#NC119-最小的K个数"><span class="nav-number">1.6.2.</span> <span class="nav-text">NC119 最小的K个数</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#NC22-合并两个有序的数组"><span class="nav-number">1.6.3.</span> <span class="nav-text">NC22 合并两个有序的数组</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#二叉树"><span class="nav-number">1.7.</span> <span class="nav-text">二叉树</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#前序遍历、中序遍历、后续遍历"><span class="nav-number">1.7.1.</span> <span class="nav-text">前序遍历、中序遍历、后续遍历</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#层次遍历"><span class="nav-number">1.7.2.</span> <span class="nav-text">层次遍历</span></a></li></ol></li></ol></li></ol></div>
            

          </div>
        </section>
      <!--/noindex-->
      

      

    </div>
  </aside>


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright"> &copy; <span itemprop="copyrightYear">2024</span>
  <span class="with-love" id="animate">
    <i class="fa fa-user"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">对美好事物的向往，心中要充满强烈的愿望！</span>

  

  
</div>




  <div class="powered-by">由 <a class="theme-link" target="_blank" href="https://hexo.io">Hexo</a> 强力驱动 v3.9.0</div>



  <span class="post-meta-divider">|</span>



  <div class="theme-info">主题 – <a class="theme-link" target="_blank" href="https://theme-next.org">NexT.Gemini</a> v6.4.2</div>




        








        
        <div>
          <a href="https://beian.miit.gov.cn/" target="_blank">闽ICP备15015722号-2</a>
        </div>
      </div>
     
    </footer>

    
      <div class="back-to-top">
        <i class="fa fa-arrow-up"></i>
        
      </div>
    

    
	
    

    
  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>


























  
  
    <script type="text/javascript" src="/blog/lib/jquery/index.js?v=2.1.3"></script>
  

  
  
    <script type="text/javascript" src="/blog/lib/velocity/velocity.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/blog/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>
  


  


  <script type="text/javascript" src="/blog/js/src/utils.js?v=6.4.2"></script>

  <script type="text/javascript" src="/blog/js/src/motion.js?v=6.4.2"></script>



  
  


  <script type="text/javascript" src="/blog/js/src/affix.js?v=6.4.2"></script>

  <script type="text/javascript" src="/blog/js/src/schemes/pisces.js?v=6.4.2"></script>



  
  <script type="text/javascript" src="/blog/js/src/scrollspy.js?v=6.4.2"></script>
<script type="text/javascript" src="/blog/js/src/post-details.js?v=6.4.2"></script>



  


  <script type="text/javascript" src="/blog/js/src/bootstrap.js?v=6.4.2"></script>



  



  










  





  

  

  

  

  

  
  

  

  

  

  

  

</body>
</html>
